package algotithm.weekendrace.biweeklycontest72.test3;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * @author tom
 * @date 2022-03-05 22:29
 */
public class Solution {

    public static void main(String[] args) {
//        int n = 8;
//        int[][] edges = {{0,3},{0,4},{1,3},{2,4},{2,7},{3,5},{3,6},{3,7},{4,6}};
        String s = "[[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]";
        String s2 = "[[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]";
//        int[][] edge = reverse(s);
        int n = 5;
        int[][] edge = reverse(s2);
        Solution solution = new Solution();
        List<List<Integer>> lists = solution.getAncestors(n, edge);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }

    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n; i++)  {
            List<Integer> list = new ArrayList<>();
            res.add(list);
        }
        for (int[] edge : edges) {
            List<Integer> list = new ArrayList<>();
            int x = edge[0];
            int y = edge[1];
            list.add(y);
            res.get(x).add(y);
        }


        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; i++)  {
            ans.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            List<Integer> list = new ArrayList<>();
//        [3,4]
            List<Integer> li = res.get(i);
            for (int j = 0; j < li.size(); j++) {
                ans.get(li.get(j)).add(i);
                // [5,6,7]
                List<Integer> integers = res.get(li.get(j));
                for (int k = 0 ; k < integers.size(); k++) {
                    ans.get(integers.get(k)).add(i);
                }
            }
        }
        for (int k = 0; k < ans.size(); k++) {
            HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
            for (int i = 0; i < ans.get(k).size(); i++) {
                if (hashMap.containsKey(ans.get(k).get(i))) {
                    ans.get(k).remove(ans.get(k).get(i));
                    continue;
                }
                hashMap.put(ans.get(k).get(i), i);
            }
        }

        return ans;
//        return res;
    }


    public static int[][] reverse(String s) {
        int n = s.length();
        char[] c = s.toCharArray();
        for (int i = 0; i < n; i++) {
            if (c[i] == '[') {
                c[i] = '{';
            } else if (c[i] == ']') {
                c[i] = '}';
            }
        }
        String[] str = new String(c).split("},");
        int m = str.length;
        int[][] res = new int[m][2];
        for (int j = 0; j < m; j++) {
            if (j == 0) {
                res[j][0] = (int) (str[j].charAt(2) - '0');
                res[j][1] = (int) (str[j].charAt(4) - '0');
            } else if (j == m - 1) {
                res[j][0] = (int) (str[j].charAt(1) - '0');
                res[j][1] = (int) (str[j].charAt(3) - '0');
            } else {
                res[j][0] = (int) (str[j].charAt(1) - '0');
                res[j][1] = (int) (str[j].charAt(3) - '0');
            }
        }
        return res;
    }
}
